package syf.binaryranktree;

public class ReviewBinarySortTree {
    public static void main(String[] args) {
        int[] arr={7,3,10,12,5,1,9,2};
        BinarySortTree binaryTree=new BinarySortTree();
        for (int i : arr) {
            binaryTree.add(new Nodes(i));
        }
        binaryTree.midShowAll();
        binaryTree.delete(7);
        System.out.println("=============结点删除后==============");
        binaryTree.midShowAll();
    }
}
//二分排序树
class BinarySortTree{
    Nodes root;
    public BinarySortTree() {
    }
    //中序遍历
    public void midShowAll(){
        if (root==null){
            System.out.println("空树");
        }else {
            root.midShowAll();
        }
    }
    //添加结点
    public void add(Nodes nodes){
        if (root==null){
            root=nodes;
        }else {
            root.addNode(nodes);
        }
    }
    /**
     * @param val 要删除的结点的值
     */
    //删除结点
    public void delete(int val){
        if (root==null){
            System.out.println("空树");
        }else {
            if (root.value==val&&root.left==null&&root.right==null){
                root=null;
            }else {
                root.deleteNode(val);
            }
        }
    }
}
//结点
class Nodes{
    Nodes left;
    Nodes right;
    int value;
    public Nodes(int value) {
        this.value = value;
    }
    @Override
    public String toString() {
        return "Nodes{" +
                "value=" + value +
                '}';
    }
    //中序遍历
    public void midShowAll(){
        if (this.left!=null){
            this.left.midShowAll();
        }
        System.out.println(this);
        if (this.right!=null){
            this.right.midShowAll();
        }
    }
    //添加结点 左边放小于等于父结点的，右边放大于父结点的
    public void addNode(Nodes nodes){
        if (nodes!=null){
            if (this.value>=nodes.value){//当前结点的值大于等于传入结点的值，往左边放
                if (this.left==null){//为空直接放即可
                    this.left=nodes;
                }else {//不为空，往左子树左遍历
                    this.left.addNode(nodes);
                }
            }else {//传入结点的值大于当前结点
                if (this.right==null){//直接放
                    this.right=nodes;
                }else {
                    this.right.addNode(nodes);
                }
            }
        }
    }
    //删除结点
    public void deleteNode(int val){
        Nodes target = this.findTarget(val);
        Nodes targetParent = this.findTargetParent(val);
        if (target==null){//没有要删除的结点
            System.out.println("没有找到要删除的结点");
        }else {
            if (targetParent!=null){//要删除的结点不为根结点
                //要删除的为叶子结点
                if (target.left==null&&target.right==null){
                    if (targetParent.left!=null&&targetParent.left==target){//判断要删除的叶子结点是否在父结点的左边
                        targetParent.left=null;
                    }else if (targetParent.right!=null&&targetParent.right==target){//判断要删除的叶子结点是否在父结点的右边
                        targetParent.right=null;
                    }
                }else if (target.left!=null&&target.right!=null){//要删除的有两个子结点，替补规则左边找最大，或者右边找最小，选择右边找最小
                    target.value= findMinVal(target.right);
                }else{//要删除的有一个子结点
                    if (targetParent.left==target&&target.left==null){//要删除的结点为父结点的左结点，且要删除结点的左结点不为空
                        targetParent.left=target.right;
                    }else if (targetParent.left==target){//要删除的结点为父结点的左结点，且要删除结点的右结点但不为空
                        targetParent.left=target.left;
                    }else if (targetParent.right==target&&target.right!=null){//要删除的结点为父结点的右结点，且要删除结点的左结点不为空
                        targetParent.right=target.right;
                    }else if (targetParent.right==target){
                        targetParent.right=target.left;
                    }
                }
            }else {//要删除的结点为根结点
                //右节点不为空
                if (target.right!=null) {
                    target.value = findMinVal(target.right);
                }else if (target.left!=null){//左结点不为空
                    target.value = findMaxVal(target.left);
                }
            }
        }
    }
    //找到要删除的结点
    public Nodes findTarget(int val){
        if (this.value==val){
            return this;
        }else {
            if (this.left!=null&&this.value>=val){//当前结点的值大于要删除的结点，往左边找
                return this.left.findTarget(val);
            }else if (this.right!=null&&this.value<val){
                return this.right.findTarget(val);
            }else {
                return null;
            }
        }
    }
    //找到要删除结点的父结点
    public Nodes findTargetParent(int val){
        if (this.left!=null&&this.left.value==val||this.right!=null&&this.right.value==val){
            return this;
        }else {
            if (this.left!=null&&this.value>=val){//当前结点的值大于要删除的结点，往左边找
                return this.left.findTargetParent(val);
            }else if (this.right!=null&&this.value<val){
                return this.right.findTargetParent(val);
            }else {
                return null;
            }
        }
    }
    //查找以传入结点为根结点树的最小值
    public int findMinVal(Nodes nodes){
        Nodes tmp=nodes;
        while (tmp.left!=null){
            tmp=tmp.left;
        }
        deleteNode(tmp.value);
        return tmp.value;//返回找到结点的值
    }
    //查找以传入结点为根结点树的最大值
    public int findMaxVal(Nodes nodes){
        Nodes tmp=nodes;
        while (tmp.right!=null){
            tmp=tmp.right;
        }
        deleteNode(tmp.value);
        return tmp.value;//返回找到结点的值
    }
}